package com.leetcode.algorithms.one.problem4;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * The median is (2 + 3)/2 = 2.5
 */
public class MedianOf2SortedArrays {
    @Test
    public void run() {
        int[] nums1 = {2};
        int[] nums2 = {};
        System.out.println(findMedianSortedArrays1(nums1, nums2));
    }

    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        int index = len / 2;
        boolean isEvenNumber = len%2==0;
        int[] arr = new int[index+1];
//        List<Integer> list = new ArrayList<>(index + 1);
        int i = 0, j = 0, k = 0;
        for (; k <= index; k++) {
            if(i==nums1.length){
                arr[k]=nums2[j++];
//                list.add(nums2[j++]);
            }else if(j==nums2.length)
                arr[k]=nums1[i++];
//                list.add(nums1[i++]);
            else if (nums1[i] < nums2[j]) {
                arr[k]=nums1[i++];
//                list.add(nums1[i++]);
            } else {
                arr[k]=nums2[j++];
//                list.add(nums2[j++]);
            }
        }
        if(isEvenNumber){
            return (arr[index]+arr[index-1])/2.0;
//            return (list.get(index)+list.get(index-1))/2.0;

        }else{
            return arr[index];
//            return list.get(index);
        }

    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        int index = len / 2;
        boolean isEvenNumber = len%2==0;
        if(nums1.length==0){
            if(isEvenNumber)
                return (nums2[index-1]+nums2[index])/2.0;
            else
                return nums2[index];
        }else if(nums2.length==0){
            if(isEvenNumber)
                return (nums1[index-1]+nums1[index])/2.0;
            else
                return nums1[index];
        }
        if(isEvenNumber)
            --index;
        int i = 0, j = 0, k = 0;
        for (; k < index; k++) {
            if (nums1[i] < nums2[j]||j==nums2.length) {
                i++;
            } else {
                j++;
            }
        }
        if(isEvenNumber){

            int small = nums1[i]<nums2[j]?nums1[i++]:nums2[j++];
            int big=0;
            if(i== nums1.length){
                big=nums2[j];
            }else if(j==nums2.length)
                big=nums1[i];
            else
             big =  nums1[i]<nums2[j]?nums1[i]:nums2[j];

            return (big+small)/2.0;

        }else{

            return nums1[i]<nums2[j]?nums1[i]:nums2[j];
        }

    }
}
